#include <utility>
#include <vector>
#include <queue>
using namespace std;

class Solution
{
private:
    // 自定义比较函数
    struct my_less_com
    {
        bool operator()(const pair<int, int> &a, const pair<int, int> &b)
        {
            return a.first + a.second < b.first + b.second;
        }
    };

public:
    vector<vector<int>> kSmallestPairs(vector<int> &nums1, vector<int> &nums2, int k)
    {
        // top k
        priority_queue<pair<int, int>, vector<pair<int, int>>, my_less_com> heap;
        for (auto a : nums1)
        {
            for (auto b : nums2)
            {
                heap.push({a, b});
                while (heap.size() > k)
                    heap.pop();
            }
        }
        vector<vector<int>> res;
        while (heap.size())
        {
            vector<int> pair_vt;
            pair_vt.push_back(heap.top().first);
            pair_vt.push_back(heap.top().second);
            res.push_back(std::move(pair_vt));
            heap.pop();
        }
        return res;
    }
};